{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 求单次买入卖出最大收益",
   "id": "d809b4ebebae6ea2"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def broughtShareOnce(arr: list) -> int | None:\n",
    "    ans: int = 0\n",
    "    length = len(arr)\n",
    "    dp = [0] * length\n",
    "    # range生成的数值范围是左闭右开的[length-2, -1)\n",
    "    for i in range(length - 2, -1, -1):\n",
    "        dp[i] = max(dp[i + 1], arr[i])\n",
    "    for i in range(length):\n",
    "        ans = max(ans, dp[i] - arr[i])\n",
    "    return ans if ans > 0 else None"
   ],
   "id": "c5e372816f575626",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "arr = random.sample(range(100), 10)\n",
    "print(arr)\n",
    "print(broughtShareOnce(arr))"
   ],
   "id": "794a235be4c56751",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 循环求最大子数组，时间复杂度O(N^2)",
   "id": "82910bf554036063"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def maximumSubArray(arr: list) -> tuple:\n",
    "    length = len(arr)\n",
    "    max_sum = 0\n",
    "    left: int = 0\n",
    "    right: int = 0\n",
    "    for i in range(length - 1):\n",
    "        temp = 0\n",
    "        for j in range(i, length):\n",
    "            temp += arr[j]\n",
    "            if temp > max_sum:\n",
    "                max_sum = temp\n",
    "                left = i\n",
    "                right = j\n",
    "    return max_sum, left, right"
   ],
   "id": "ed34327733fef384",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "arr = random.sample(range(-100, 100), 10)\n",
    "print(arr)\n",
    "print(maximumSubArray(arr))"
   ],
   "id": "781a2b7d349abbee",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 分治策略求最大子数组",
   "id": "7cb90408d2e02f1c"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def findMaximumSubArray(arr: list, low: int, high: int):\n",
    "    if high == low:\n",
    "        print(low)\n",
    "        return low, high, arr[low]\n",
    "    else:\n",
    "        mid = int((low + high) // 2)\n",
    "        (left_low, left_high, left_sum) = findMaximumSubArray(arr, low, mid)\n",
    "        (right_low, right_high, right_sum) = findMaximumSubArray(arr, mid + 1, high)\n",
    "        (cross_low, cross_high, cross_sum) = findMaxCrossingSubArray(arr, low, mid, high)\n",
    "        if left_sum >= right_sum and left_sum >= cross_sum:\n",
    "            return left_low, left_high, left_sum\n",
    "        elif right_sum >= cross_sum:\n",
    "            return right_low, right_high, right_sum\n",
    "        else:\n",
    "            return cross_low, cross_high, cross_sum\n",
    "\n",
    "\n",
    "def findMaxCrossingSubArray(arr: list, low: int, high: int, mid: int):\n",
    "    leftSum = 0\n",
    "    sum = 0\n",
    "    maxLeft = mid\n",
    "    for i in range(mid, low - 1, -1):\n",
    "        sum += arr[i]\n",
    "        if sum > leftSum:\n",
    "            leftSum = sum\n",
    "            maxLeft = i\n",
    "\n",
    "    sum = 0\n",
    "    maxRight = mid + 1\n",
    "    rightSum = 0\n",
    "    for i in range(mid + 1, high):\n",
    "        sum += arr[i]\n",
    "        if sum > rightSum:\n",
    "            rightSum = sum\n",
    "            maxRight = i\n",
    "    return maxLeft, maxRight, rightSum + leftSum"
   ],
   "id": "f7d67ca4338bdc70",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "arr = random.sample(range(-100, 100), 10)\n",
    "print(arr)\n",
    "print(findMaximumSubArray(arr, 0, len(arr) - 1))"
   ],
   "id": "f27867703b30afa0",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "#### 一维数组转二维数组",
   "id": "fde54bf531ebb36c"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def dimOne22(arr: list[int], row: int, col: int) -> list[list[int]]:\n",
    "    return [[arr[i] for i in range(j * row, j * row + row)] for j in range(col)]"
   ],
   "id": "b1a53e1e58ff24f3",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "row = 4\n",
    "col = 2\n",
    "arr = random.sample(range(-100, 100), row * col)\n",
    "arr2 = [random.sample(range(-100, 100), row) for _ in range(col)]\n",
    "print(arr)\n",
    "print(arr2)\n",
    "towDimArray = dimOne22(arr, row, col)\n",
    "print(towDimArray)"
   ],
   "id": "e9d01e5bd4039d3",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 二维矩阵的乘法",
   "id": "b015127d36deb336"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def squareMatrixMultple(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:\n",
    "    rowA = len(A)\n",
    "    colA = len(A[0])\n",
    "    rowB = len(B)\n",
    "    colB = len(B[0])\n",
    "    C: list[list[int]] = [[0] * colB for _ in range(rowA)]\n",
    "    assert colA == rowB\n",
    "    for i in range(rowA):\n",
    "        for j in range(colB):\n",
    "            for k in range(colA):\n",
    "                C[i][j] += A[i][k] * B[k][j]\n",
    "    return C"
   ],
   "id": "b3a017e27c1c9ee1",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "rowA = 3\n",
    "colA = 4\n",
    "rowB = 4\n",
    "colB = 3\n",
    "A = [random.sample(range(-100, 100), colA) for _ in range(rowA)]\n",
    "B = [random.sample(range(-100, 100), colB) for _ in range(rowB)]\n",
    "print(A)\n",
    "print(B)\n",
    "C = squareMatrixMultple(A, B)\n",
    "print(C)"
   ],
   "id": "e9e7c55a822c14f",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 简单的递归分治计算矩阵乘法的算法(❌)\n",
    "基于以下公式：\n",
    "\n",
    "![](https://raw.githubusercontent.com/sorhkej/pic-board/main/20240429132309.png?token=APCAT477ORMEP4YLMJ5YWC3GF4XPY)"
   ],
   "id": "c8df7a12d9b33402"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "# 利用python中=传的是引用，[:]传的是视图（不会深拷贝）的设计\n",
    "# 将原本一个大的二维数组“切割”成一个小的二维数组并返回其视图\n",
    "class SubMatrix:\n",
    "\n",
    "    def __init__(self, row: int, matrix: list[list[int]] = None):\n",
    "        if matrix is None:\n",
    "            self.matrix = [[0] * row for _ in range(row)]\n",
    "        else:\n",
    "            self.matrix = matrix\n",
    "        self.row = row\n",
    "        self.col = row\n",
    "        self.subRow = row\n",
    "        self.subCol = row\n",
    "        self.pointX = 0\n",
    "        self.pointY = 0\n",
    "\n",
    "    def subMatrixView(self) -> list[list[int]]:\n",
    "        return self.matrix[self.pointX:self.pointX + self.subRow][self.pointY:self.pointY + self.subCol]\n",
    "\n",
    "    def subMatrixAdd(self, ma: list[list[int]]) -> None:\n",
    "        self.subMatrixView()[:] = [a + b for a, b in zip(self.subMatrixView(), ma)]\n"
   ],
   "id": "bb32769d49cfd93",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def subMatrixCal(A: SubMatrix, B: SubMatrix, C: SubMatrix | None) -> None:\n",
    "    if C is None:\n",
    "        C = SubMatrix(A.row)\n",
    "\n",
    "    if A.subRow == 1:\n",
    "        C.subMatrixView()[0][0] += A.subMatrixView()[0][0] * B.subMatrixView()[0][0]\n",
    "    elif A.subRow == 2:\n",
    "        mC = C.subMatrixView()\n",
    "        mA = A.subMatrixView()\n",
    "        mB = B.subMatrixView()\n",
    "        mC[0][0] += mA[0][0] * mB[0][0] + mA[0][1] * mB[1][0]\n",
    "        mC[0][1] += mA[0][0] * mB[0][1] + mA[0][1] * mB[1][1]\n",
    "        mC[1][0] += mA[1][0] * mB[0][0] + mA[1][1] * mB[1][0]\n",
    "        mC[1][1] += mA[1][0] * mB[0][1] + mA[1][1] * mB[1][1]\n",
    "    else:\n",
    "        subRow = A.subRow // 2\n",
    "        A.subCol = subRow\n",
    "        A.subRow = subRow\n",
    "        B.subCol = subRow\n",
    "        B.subRow = subRow\n",
    "        C.subCol = subRow\n",
    "        C.subRow = subRow\n",
    "\n",
    "        # C11 + A11 * B11\n",
    "        subMatrixCal(A, B, C)\n",
    "\n",
    "        # C11 + A12 * B21\n",
    "        A.pointX += subRow\n",
    "        B.pointY += subRow\n",
    "        subMatrixCal(A, B, C)\n",
    "        B.pointY -= subRow\n",
    "        A.pointX -= subRow\n",
    "\n",
    "        # C12 + A11 * B12\n",
    "        C.pointX += subRow\n",
    "        B.pointX += subRow\n",
    "\n",
    "        subMatrixCal(A, B, C)\n",
    "\n",
    "        # C12 + A12 * B22 \n",
    "        A.pointX += subRow\n",
    "        B.pointY += subRow\n",
    "        subMatrixCal(A, B, C)\n",
    "        A.pointX -= A.subRow\n",
    "        B.pointY -= subRow\n",
    "\n",
    "        B.pointX -= subRow\n",
    "        C.pointX -= subRow\n",
    "\n",
    "        # C21 + A21 * B11\n",
    "        C.pointY += subRow\n",
    "        A.pointY += subRow\n",
    "\n",
    "        subMatrixCal(A, B, C)\n",
    "\n",
    "        # C21 + A22 * B21\n",
    "        A.pointX += subRow\n",
    "        B.pointY += subRow\n",
    "        subMatrixCal(A, B, C)\n",
    "        B.pointY -= subRow\n",
    "        A.pointY -= subRow\n",
    "\n",
    "        # C22 + A21 * B12\n",
    "        C.pointX += subRow\n",
    "        B.pointX += subRow\n",
    "        subMatrixCal(A, B, C)\n",
    "        # C22 + A22 * B22\n",
    "        A.pointY += subRow\n",
    "        B.pointX += subRow\n",
    "        subMatrixCal(A, B, C)\n",
    "        A.pointX -= subRow\n",
    "        B.pointX -= subRow\n",
    "        C.pointX -= subRow\n",
    "        A.pointY -= subRow\n",
    "        B.pointY -= subRow\n",
    "        C.pointY -= subRow\n"
   ],
   "id": "492c2f71a2e7153d",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "colA = 4\n",
    "rowA = 4\n",
    "A = [random.sample(range(-100, 100), colA) for _ in range(rowA)]\n",
    "subA = SubMatrix(rowA, A)\n",
    "# print(subA.subRow)\n",
    "B = [random.sample(range(-100, 100), colA) for _ in range(rowA)]\n",
    "subB = SubMatrix(rowA, B)\n",
    "print(subMatrixCal(subA, subA, None))"
   ],
   "id": "dbab055431c2a0a6",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 简单的分治求两个矩阵相乘的算法",
   "id": "d3a8dad84a5cbd22"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "# 两个相同结构的二维数组相加\n",
    "def matrixAdd(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:\n",
    "    return [[A[i][j] + B[i][j] for j in range(len(A[0]))] for i in range(len(A))]"
   ],
   "id": "a49ca09fee485a6b",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "# 获取指定范围的方阵视图，以A上startX，startY为起点，边长为length的视图\n",
    "def getMatrixView(A: list[list[int]], length: int, startX: int, startY: int) -> list[list[int]]:\n",
    "    temp = [[]] * length\n",
    "    for i in range(length):\n",
    "        temp[i] = A[startX + i][startY:startY + length]\n",
    "    return temp"
   ],
   "id": "bc67dc644015dea6"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "# 两个二维数组相乘，约束：矩阵为方阵，且行数只能为2的幂次\n",
    "def mergeMatrixMultiply(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:\n",
    "    n = len(A)\n",
    "    if n == 1:\n",
    "        return [[A[0][0] * B[0][0]]]\n",
    "    elif n == 2:\n",
    "        return [[A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],\n",
    "                [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]]\n",
    "    else:\n",
    "        mid = n // 2\n",
    "        A11 = getMatrixView(A, mid, 0, 0)\n",
    "        A12 = getMatrixView(A, mid, 0, mid)\n",
    "        A21 = getMatrixView(A, mid, mid, 0)\n",
    "        A22 = getMatrixView(A, mid, mid, mid)\n",
    "\n",
    "        B11 = getMatrixView(B, mid, 0, 0)\n",
    "        B12 = getMatrixView(B, mid, 0, mid)\n",
    "        B21 = getMatrixView(B, mid, mid, 0)\n",
    "        B22 = getMatrixView(B, mid, mid, mid)\n",
    "\n",
    "        C11 = matrixAdd(mergeMatrixMultiply(A11, B11), mergeMatrixMultiply(A12, B21))\n",
    "        C12 = matrixAdd(mergeMatrixMultiply(A11, B12), mergeMatrixMultiply(A12, B22))\n",
    "        C21 = matrixAdd(mergeMatrixMultiply(A21, B11), mergeMatrixMultiply(A22, B21))\n",
    "        C22 = matrixAdd(mergeMatrixMultiply(A21, B12), mergeMatrixMultiply(A22, B22))\n",
    "        # 将子方阵拼接为一个完整方阵，先进行列拼接后进行行拼接\n",
    "        return [C11[i] + C12[i] for i in range(len(C11))] + [C21[i] + C22[i] for i in range(len(C11))]"
   ],
   "id": "1f7751b4dc8346c5"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "colA = 4\n",
    "rowA = 4\n",
    "A = [random.sample(range(-100, 100), colA) for _ in range(rowA)]\n",
    "B = [random.sample(range(-100, 100), colA) for _ in range(rowA)]\n",
    "print(mergeMatrixMultiply(A, B))"
   ],
   "id": "e2b1a06454ae38f7",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 设计算法，仅使用三次实数乘法即可完成复数a+bi与c+di相乘。",
   "id": "778abf0bd9d68370"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "def imageMutiply(a,b,c,d):\n",
    "    ac = a * c\n",
    "    bd = b * d\n",
    "    ad_bc = (a + b) * (c + d) - ac - bd\n",
    "    \n",
    "    real = ac - bd\n",
    "    imag = ad_bc\n",
    "    # ad+bc,ac-bd\n",
    "    return real,imag"
   ],
   "id": "f7f220e8dae499c9"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-04-30T06:06:39.152141Z",
     "start_time": "2024-04-30T06:06:39.120427Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import inspect\n",
    "def readMulMatrixSource():\n",
    "    print(\"hello\")\n",
    "    print(inspect.getfile(list.__sizeof__))\n",
    "readMulMatrixSource()"
   ],
   "id": "6248a06e9b238476",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "module, class, method, function, traceback, frame, or code object was expected, got method_descriptor",
     "output_type": "error",
     "traceback": [
      "\u001B[1;31m---------------------------------------------------------------------------\u001B[0m",
      "\u001B[1;31mTypeError\u001B[0m                                 Traceback (most recent call last)",
      "Cell \u001B[1;32mIn[19], line 5\u001B[0m\n\u001B[0;32m      3\u001B[0m     \u001B[38;5;28mprint\u001B[39m(\u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mhello\u001B[39m\u001B[38;5;124m\"\u001B[39m)\n\u001B[0;32m      4\u001B[0m     \u001B[38;5;28mprint\u001B[39m(inspect\u001B[38;5;241m.\u001B[39mgetfile(\u001B[38;5;28mlist\u001B[39m\u001B[38;5;241m.\u001B[39m__sizeof__))\n\u001B[1;32m----> 5\u001B[0m readMulMatrixSource()\n",
      "Cell \u001B[1;32mIn[19], line 4\u001B[0m, in \u001B[0;36mreadMulMatrixSource\u001B[1;34m()\u001B[0m\n\u001B[0;32m      2\u001B[0m \u001B[38;5;28;01mdef\u001B[39;00m \u001B[38;5;21mreadMulMatrixSource\u001B[39m():\n\u001B[0;32m      3\u001B[0m     \u001B[38;5;28mprint\u001B[39m(\u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mhello\u001B[39m\u001B[38;5;124m\"\u001B[39m)\n\u001B[1;32m----> 4\u001B[0m     \u001B[38;5;28mprint\u001B[39m(inspect\u001B[38;5;241m.\u001B[39mgetfile(\u001B[38;5;28mlist\u001B[39m\u001B[38;5;241m.\u001B[39m__sizeof__))\n",
      "File \u001B[1;32mD:\\Python\\Anaconda\\Lib\\inspect.py:920\u001B[0m, in \u001B[0;36mgetfile\u001B[1;34m(object)\u001B[0m\n\u001B[0;32m    918\u001B[0m \u001B[38;5;28;01mif\u001B[39;00m iscode(\u001B[38;5;28mobject\u001B[39m):\n\u001B[0;32m    919\u001B[0m     \u001B[38;5;28;01mreturn\u001B[39;00m \u001B[38;5;28mobject\u001B[39m\u001B[38;5;241m.\u001B[39mco_filename\n\u001B[1;32m--> 920\u001B[0m \u001B[38;5;28;01mraise\u001B[39;00m \u001B[38;5;167;01mTypeError\u001B[39;00m(\u001B[38;5;124m'\u001B[39m\u001B[38;5;124mmodule, class, method, function, traceback, frame, or \u001B[39m\u001B[38;5;124m'\u001B[39m\n\u001B[0;32m    921\u001B[0m                 \u001B[38;5;124m'\u001B[39m\u001B[38;5;124mcode object was expected, got \u001B[39m\u001B[38;5;132;01m{}\u001B[39;00m\u001B[38;5;124m'\u001B[39m\u001B[38;5;241m.\u001B[39mformat(\n\u001B[0;32m    922\u001B[0m                 \u001B[38;5;28mtype\u001B[39m(\u001B[38;5;28mobject\u001B[39m)\u001B[38;5;241m.\u001B[39m\u001B[38;5;18m__name__\u001B[39m))\n",
      "\u001B[1;31mTypeError\u001B[0m: module, class, method, function, traceback, frame, or code object was expected, got method_descriptor"
     ]
    }
   ],
   "execution_count": 19
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
